00100	Some general considerations behind representation of shape:
00200		volume not surface representation
00300			question of dimensionality-proper dimension
00400			that is, we want to represent the interior
00500			of our laser-scan data, not the boundary.
00600			We want to evaluate whether the profiles are
00700			included in descriptions, not whether the
00800			boundary is included in descriptions.
00900		high level vs low level descriptions
01000			we can identify high and low level with
01100			object space and image space descriptions.
01200			
01300	
01400	
01500	
01600	
01700	
01800	some practical approaches to description
01900		sample coarsely, form a "global" model, then verify
01950			start with ends?
01975			length to width ratio
02000		describe the profiles, not the boundary
     

00100	It is now more or less accepted that a representation like
00200	that of Agin, Nevatia  and Binford is a prime candidate for
00300	a system representation for complex objects.  The question
00400	of representation of cross sections is most clearly resolved
00500	in terms of that doctrine.
00600	
00700	If we believe the doctrine, the representation of areas in
00800	two dimensions is a representation problem of the same sort
00900	in one lower dimension.  The first step is segmentation
01000	with cutting and pasting.  The choice of primitive elements
01100	is now raised in two dimensions instead of three.  The doctrine
01200	tells us to look for a cross-section defined along a space curve.
01300	That cross-section is one-dimensional, a line, and the space
01400	curve is defined in two dimensions.  Of course, circles would
01500	be added as a primitive.
01600	
01700	When we look at the alternate forms of representation, they might be:
01800		1.  expansions (spline,Fourier,moments....)
01900		2.  spatial domain tables (r vs theta)
02000		3.  templates, with modifications
02100		4.  feature list (not closely organized)
02200		5.  boundary curve (trouble with closure-leads to syntax)
02300	We have agreed that splines and other expansions are of dubious value for
02400	recognition and similarity operations.  They also tend to be associated with
02500	unarticulated descriptions.  Spatial domain tables are rather alike.  They
02600	also can be useful in special cases.  They do have some advantages in not
02700	losing locality.  Saying templates is not enough.  We must specify their
02800	representation, which must be one of those techniques.  Feature lists are
02900	a vague way of pointing at the extreme form of network descriptions.  All
03000	our representations will be some network.  Whether the arcs are set properties
03100	or geometrical measurements is significant.  If we try to get along with
03200	set membership (MUST-HAVE) or boolean geometrical properties (LEFT-OF)
03300	then we will not do well.
03400	Finally, we have the boundary curve representation.  We make a comparison
03500	between representing an area by its boundary(curve), and representing a volume
03600	by its boundary (surface).  We contend that in three dimensions for strong
03700	and profound reasons, that representing volume is the right thing to do,
03800	not represent the cuts in the volume.  The same thing is true for two dimensions,
03900	that we must represent the area and not the cuts in two dimensions.  There
04000	are quite important properties which are not well-expressed by surface
04100	representations in three-dimensions and curve representations in two dimensions
04200	which do have simple expression in the cross section representation.
04300	To give an example from two dimensions, which has an obvious counterpart in
04400	three dimensions.  Suppose I want to describe polygons by a curve description.
04500	Nothing easier.  I have a string, L1,A1,L2,A2,L3,A3,...
04600	of lengths Li and angles Ai. Now I just make up a grammar and we win big.
04700	Question: does a string make a realizable polygon, does it cross and does
04800	it close?  Question:  where is a thin part to pick up the object?  How would
04900	I make up an approximate description of lesser quality-is it still realizable?
05000	We see that those are non-local computations with the boundary string description
05100	but that they are better behaved with the cross section along an axis
05200	representation.  That is, to see that the axis does not cross is a global
05300	property, but we can use local properties to answer local questions:
05400	is the shape locally realizable?  where is the shape thin?
     

00100	As a problem for exercising AI languages,  we  would  like  a  choice
00200	which  tests  specific  language features.  It is also useful to know
00300	that the features used are of  real  significance  to  AI,  not  just
00400	formally convenient or familiar.  The criteria might be:
00500		requires representation of a coherent body of knowledge
00600		requires planning rather than a searching solution
00700		allows convenient suggestion of heuristic knowledge
00800		takes account of serendipity
00900		has real-world input.
01000	
01100	The problem I propose is to create perceptual strategies for locating
01200	objects  from  their symbolic descriptions in my representation which
01300	is being used for description of the shape of  complex  objects.   We
01400	are  given  some objects in a visual world, and representation of the
01500	objects and what we know about their position,  location,  (lighting,
01600	color,  etc).   We  have  some  visual operations (lines, contouring,
01700	curve fitting, verification,..) and descriptions  of  when  they  are
01800	appropriate.   Generate  a  program  which  will  locate  a specified
01900	object.
02000	
02100	The object we have in mind is the water pump which is being  used  by
02200	hand/eye.   Locate  the  body  of the pump.  Give its orientation and
02300	position accurately enough that it can be  picked  up  by  the  hand.
02400	Locate the cover (which has a long shaft) for the same purpose.
02500	
     

00100	THE REPRESENTATION OF SHAPE
00200	
00300	The  representation  [Binford  1971]depends  upon   segmentation   to
00400	describe  complex  objects  in  terms of parts. The representation is
00500	graph-structured: nodes correspond to parts, while arcs correspond to
00600	relations  between  parts.    Parts are themselves structures of this
00700	form.  The relations include relative position and  orientation,  the
00800	degrees  of  freedom,  symmetry,  and any detailed knowledge of joint
00900	structure.  Examples are neck joint, shoulder joint, and hip joint of
01000	a human.
01100	
01200	The topological operations of cutting and pasting are used in joining
01300	parts.      Normally,  we  think  of  holes  as  made  by  cuts   and
01400	protuberances  as  made by pasting; this can be done purely formally,
01500	but we would like to generalize that to a choice between the  simpler
01600	of  structures,  with cuts or glue.  In fabrication, cutting is often
01700	used to form even complicated  protuberances;  attaching  seems  more
01800	difficult,  particularly  when dimensional accuracy is necessary. The
01900	representation  reflects  some  fabrication  operations,  and  allows
02000	embedding  of  heuristic  knowledge.     The representations resemble
02100	construction algorithms.   But we would not  expect  that  reasonable
02200	construction   algorithms   could   emerge  until  a  micro-world  of
02300	fabrication operations is available for evaluation of simplicity.
02400	
02500	We have concentrated on the inverse  problem  of  building  up  these
02600	structures  from visual data.  When possible, the choice of parts and
02700	description of joint relations uses whatever knowledge is  available.
02800	When  guesses  are  necessary,  we  have a number of heuristics which
02900	correspond to our intuition about shape.
03000	
03100	The primitive parts are  described  by  volume  representations.   We
03200	maintain that a useful choice of parts is in terms of arm-like parts,
03300	which come naturally from the representation. The primitive parts are
03400	described  by "generalized local cones".  These are the volumes swept
03500	out by taking an arbitrary cross section and translating it  along  a
03600	path,  maintaining  the  cross  section normal to the path, while the
03700	scale of the cross section is changed smoothly.  The  basis  of  this
03800	representation is the description of a large class of shapes based on
03900	transformation of  local  descriptions.  The  typical  element  is  a
04000	snake-like  piece,  described by an axis (which is a space curve) and
04100	normal cross sections.   The cross  sections  are  arbitrary.   Local
04200	cylinders,  cones,  toroids,  and  helices,  all with arbitrary cross
04300	sections, are typical examples.
04400	
04405	The process of segmentation allows non-unique representations.  This
04410	permits a choice of simple representations; we can regard it as an
04415	advantage that we have such a choice.
04500	We have a simplicity criterion of shapes based on the  transformation
04600	function   on  the  cross  section  (constant=cylinder,  linear=cone,
04700	monotonic, convex, single maximum, shape changing...).
04800	
04900				MAN
05000	
05100	
05200				<SHOULDERS>
05300				   |
05400				 <HIPS>
05500	
05600	
05700				
05800			       [HEAD]
05900				 |
06000				NECK
06100				 |
06200		      [ARM]--<SHOULDERS>--[ARM]
06300				 |
06400			       TRUNK
06500				 |
06600			      <HIPS>
06700			      |    |
06800			  [LEG]    [LEG]
06900	
07000	
07100	
07200	
07300	
07400	and ARM is:		ARM
07500	
07600			     UPPER ARM
07700				|
07800			      <ELBOW>
07900				|
08000			     FOREARM
08100				|
08200			     <WRIST>
08300				|
08400			      <HAND>
08500		  |	   |	    |	      |	      |
08600		[FINGER] [FINGER] [FINGER] [FINGER] [THUMB]
08700	
08800	
08900	
09000	A primitive has the representation:
09100	
09200			FOREARM
09300		    |	  |      |
09400		CROSS	AXIS	TRANSFORMATION
09500	       SECTION
09600	
09700	The  primary  considerations  for  the  utility of the representation
09800	concern the tasks we will  need  to  perform.   These  tasks  can  be
09900	described in various ways; the most enlightening description of tasks
10000	is in terms of their computational structure.   For  these  problems,
10100	topological  and  geometric  considerations  are  important.  Surface
10200	representations have been used for display  purposes.   For  robotics
10300	applications,  the representation for manipulation would need to make
10400	explicit how to pick up an object, i.e. where is the center of  mass,
10500	the  center  of rotation, and what are the moments.  How thick is the
10600	piece, and how long?  These are more than  just  surface  properties,
10700	and  the  surface  representation  is  no  help  in determining these
10800	properties. These properties are the sort  of  properties  which  are
10900	natural  for  our  volume representations; however surface properties
11000	are quite naturally obtained in this representation.
11100	
11200	The  cross  sections  are  represented  in  the  same  fashion in two
11205	dimensions as  objects  are  in  three  dimensions.   The  part/whole
11210	segmentation  is  crucial.    The parts which are useful are not just
11215	curves,  but  arm-like  areas.  Thus  we  are  interested   in   area
11220	representations, not curve representations. The descriptions in terms
11225	of a two-dimensional  axis  and  width  are  similar  to  the  volume
11230	representations.
12000	
12100			CROSS SECTION
12200		[AREA-PART]--<JOINT>--[AREA-PART]
12300	
12400	
12500	where a part of a cross section is an area defined  by  subparts.   A
12600	primitive part is defined by:
12700			    PRIMITIVE AREA-PART
12800			|	|	|	|
12900		     WIDTH    AXIS   TRANS   SURFACE
13000					     PROPERTIES
13100	
13200	The pump can be described by:
13300				PUMP
13400	
13500	
13600		    SCREWS-----[HOUSING]----SCREWS
13700		     |		  |	      |
13800		     |	       <MATING>	      |
13900		     |		  |	      |
14000		     |----------[GASKET]------|
14100		     |		  |	      |
14200		     |		<MATING>      |
14300		     |		  |	      |
14400		     |----------[TOP]---------|
14500	
14600	The housing description is the basis of our prediction mechanism:
14700	
14800				[HOUSING]
14900	
15000	
15100	
15200	
15300		IMPELLER------PLATE-------SCREW HOLES
15400		  HOLE     |	   |
15500		HOLE IN ---	[BODY]
15600		2ND CHAMBER
15700	
15800	The coordinate system is local to each element.  That is,
15900	each link contains a transformation required to go from the
16000	coordinate system of one element at a joint at one end, to the
16100	coordinate system of an element at the joint at the other end.
16200	This is a translation combined with a rotation.  It is most
16300	convenient to define the local coordinates in terms of actual
16400	vectors rather than with an arbitrary basis.